package main

import (
	"fmt"
)

// 插入排序 :
// 把n个待排序的数组看成一个有序和无序的数组，
// 开始的时候 有序的数组只有一个元素，无序的数组n-1个
// 每次从无序的数组中取出一个数组，在有序数组中排序

func insertSort(arr *[9]int) {
	if len(arr) <= 1 {
		// return arr
	} else {
		for i := 1; i < len(arr); i++ {
			tmp := arr[i]
			insertIndex := i - 1
			for insertIndex >= 0 && tmp < arr[insertIndex] {
				arr[insertIndex+1] = arr[insertIndex]
				insertIndex--
			}

			arr[insertIndex+1] = tmp
			fmt.Println(arr)

		}
	}
}

func main() {

	arr := [9]int{3, 5, 4, 2, 9, 6, 78, 9, 10}

	insertSort(&arr)
	fmt.Println(arr)

}
